/*
最大堆:  i  parent:(i-1)/2
           left: 2*i+1,  right: 2*i+2
 */

function swap (arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

class MaxHeap {
  constructor () {
    this.data = []
  }

  size () {
    return this.data.length
  }

  isEmpty () {
    return this.size() === 0
  }

  _parent (index) {
    if (index <= 0) {
      throw new Error('index <= 0, does not have parent')
    } else {
      return parseInt((index - 1) / 2 + '')
    }
  }

  _left (index) {
    return 2 * index + 1
  }

  _right (index) {
    return 2 * index + 2
  }

  /*
  添加元素，最后位置添加，然后将最后的位置的元素做sift up操作
   */
  add (element) {
    this.data.push(element)
    this._siftUp(this.size() - 1)
  }

  _siftUp (index) {
    while (index > 0 && this.data[index] > this.data[this._parent(index)]) {
      swap(this.data, index, this._parent(index))
      index = this._parent(index)
    }
  }

  /**
   * 查看堆顶元素
   * @return {*}
   */
  peek () {
    return this.data[0]
  }

  /*
  取出元素(堆顶)
  思路: 将堆顶元素(index=0)和末尾元素交换，末尾元素做sift down操作
   */
  extractMax () {
    swap(this.data, 0, this.size() - 1)
    const result = this.data.pop()
    this._siftDown(0)
    return result
  }

  _siftDown (index) {
    while (this._left(index) < this.size()) {
      let maxIndex = this._left(index)
      let maxValue = this.data[this._left(index)]
      if (this._right(index) < this.size() && maxValue < this.data[this._right(index)]) {
        // 如果存在右结点，并且右结点比左还大
        maxIndex = this._right(index)
        maxValue = this.data[this._right(index)]
      }
      if (maxValue < this.data[index]) {
        // 不需要再sift down了
        break
      }
      swap(this.data, index, maxIndex)
      index = maxIndex
    }
  }

  /*
  取出堆中最大元素，替换成element
   */
  replace (element) {
    const value = this.peek()
    this.data[0] = element
    this._siftDown(0)
    return value
  }

  /*
  heapify: 将任意数组整理成堆的结构
  思路: 从最后一个非叶子结点(lastIndex的父节点)开始向前做siftDown
   */
  heapify (arr) {
    this.data = arr
    for (let index = this._parent(this.size() - 1); index >= 0; index--) {
      this._siftDown(index)
    }
  }
}

export default MaxHeap
